#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
class Solution {
public:
    bool isValid(string s) {
        stack<char> sta;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')sta.push(s[i]);
            else
            {
                if (sta.empty())return 0;
                if (s[i] == ')')
                {
                    if (sta.top() == '(')sta.pop();
                    else return 0;
                    continue;
                }
                if (s[i] == ']')
                {
                    if (sta.top() == '[')sta.pop();
                    else return 0;
                    continue;
                }
                if (s[i] == '}')
                {
                    if (sta.top() == '{')sta.pop();
                    else return 0;
                    continue;
                }
            }
        }
        return sta.empty();
    }
};
int main()
{
    Solution sol;
    cout << sol.isValid("()()()[[{}]]") << endl;
}